function generateRandomScores(numStudents, numSubjects) {
  let students = [];
  for (let i = 0; i < numStudents; i++) {
      let scores = [];
      for (let j = 0; j < numSubjects; j++) {
          scores.push(Math.floor(Math.random() * 41) + 60);  // 生成0到140的随机成绩
      }
      students.push(scores);
  }
  return students;
}

function initializeClasses(students, numClasses) {
  let classes = Array.from({ length: numClasses }, () => []);
  let shuffled = students.slice().sort(() => Math.random() - 0.5); // 随机打乱学生顺序

  shuffled.forEach((student, index) => {
      classes[index % numClasses].push(student);
  });

  return classes;
}

function calculateClassAvg(classScores, numSubjects) {
  let avgScores = Array(numSubjects).fill(0);
  
  classScores.forEach(scores => {
      scores.forEach((score, i) => {
          avgScores[i] += score;
      });
  });

  return avgScores.map(sum => sum / classScores.length);
}

function calculateMaxAvgDiff(classes, numSubjects) {
  let subjectAvgs = Array.from({ length: numSubjects }, () => []);

  classes.forEach(cls => {
      let classAvg = calculateClassAvg(cls, numSubjects);
      classAvg.forEach((avg, i) => {
          subjectAvgs[i].push(avg);
      });
  });

  let maxDiffs = subjectAvgs.map(avgs => Math.max(...avgs) - Math.min(...avgs));
  return maxDiffs;
}

function swapStudents(classes) {
  let [class1, class2] = [Math.floor(Math.random() * classes.length), Math.floor(Math.random() * classes.length)];
  if (class1 !== class2 && classes[class1].length > 0 && classes[class2].length > 0) {
      let [idx1, idx2] = [Math.floor(Math.random() * classes[class1].length), Math.floor(Math.random() * classes[class2].length)];
      [classes[class1][idx1], classes[class2][idx2]] = [classes[class2][idx2], classes[class1][idx1]];
  }
}

function safeExp(value) {
  return Math.exp(Math.max(-700, Math.min(700, value)));  // 限制指数函数的输入范围
}

function simulatedAnnealing(students, numClasses, numSubjects, initialTemp, coolingRate, iterations) {
  let currentSolution = initializeClasses(students, numClasses);
  let currentMaxDiffs = calculateMaxAvgDiff(currentSolution, numSubjects);
  
  let bestSolution = JSON.parse(JSON.stringify(currentSolution));
  let bestMaxDiffs = currentMaxDiffs.slice();
  
  let temp = initialTemp;

  for (let i = 0; i < iterations; i++) {
      let newSolution = JSON.parse(JSON.stringify(currentSolution));
      swapStudents(newSolution);
      let newMaxDiffs = calculateMaxAvgDiff(newSolution, numSubjects);
      
      // 比较是否接受新方案
      let accept = newMaxDiffs.every((newDiff, index) => newDiff < currentMaxDiffs[index]) ||
          Math.random() < safeExp((currentMaxDiffs.reduce((a, b) => a + b, 0) - newMaxDiffs.reduce((a, b) => a + b, 0)) / temp);

      if (accept) {
          currentSolution = newSolution;
          currentMaxDiffs = newMaxDiffs;
          
          if (currentMaxDiffs.reduce((a, b) => a + b, 0) < bestMaxDiffs.reduce((a, b) => a + b, 0)) {
              bestSolution = JSON.parse(JSON.stringify(currentSolution));
              bestMaxDiffs = currentMaxDiffs.slice();
          }
      }

      // 降低温度
      temp *= coolingRate;
      if (temp < 1e-8) {
          temp = 1e-8;
      }
  }

  return { bestSolution, bestMaxDiffs };
}

// 参数配置
const numStudents = 911;
const numSubjects = 7;
const numClasses = 10;
const initialTemp = 1000;
const coolingRate = 0.995;
const iterations = 10000;

// 执行算法
let students = generateRandomScores(numStudents, numSubjects);
let { bestSolution, bestMaxDiffs } = simulatedAnnealing(students, numClasses, numSubjects, initialTemp, coolingRate, iterations);

// 输出最终结果
bestSolution.forEach((cls, index) => {
  let avgScores = calculateClassAvg(cls, numSubjects);
  console.log(`班级 ${index + 1} 的各科平均成绩: ${avgScores.map((avg, i) => `科目 ${i + 1}: ${avg.toFixed(2)}`).join(', ')}`);
});

console.log(`最终的最大平均分差异: ${bestMaxDiffs.map((diff, i) => `科目 ${i + 1}: ${diff.toFixed(2)}`).join(', ')}`);
